|
In mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic (PA), first set out in R. M. Robinson (1950). Q is essentially PA without the axiom schema of induction. Since Q is weaker than PA but it has the same language, it is incomplete. Q is important and interesting because it is a finitely axiomatized fragment of PA that is recursively incompletable and essentially undecidable. ==Axioms== The background logic of Q is first-order logic with identity, denoted by infix '='. The individuals, called natural numbers, are members of a set called N with a distinguished member 0, called zero. There are three operations over N: *A unary operation called successor and denoted by prefix ''S''; *Two binary operations, addition and multiplication, denoted by infix + and by concatenation, respectively. The following axioms for Q are Q1–Q7 in Burgess (2005: 56), and are also the first seven axioms of first order arithmetic. Variables not bound by an existential quantifier are bound by an implicit universal quantifier. # ''Sx'' ≠ 0 # *0 is not the successor of any number. # (''Sx'' = ''Sy'') → ''x'' = ''y'' # * If the successor of ''x'' is identical to the successor of ''y'', then ''x'' and ''y'' are identical. (1) and (2) yield the minimum of facts about N (it is an infinite set bounded by 0) and ''S'' (it is an injective function whose domain is N) needed for non-triviality. The converse of (2) follows from the properties of identity. # ''y''=0 ∨ ∃''x'' (''Sx'' = ''y'') # * Every number is either 0 or the successor of some number. The axiom schema of mathematical induction present in arithmetics stronger than Q turns this axiom into a theorem. # ''x'' + 0 = ''x'' # ''x'' + ''Sy'' = ''S''(''x'' + ''y'') # * (4) and (5) are the recursive definition of addition. # ''x''·0 = 0 # ''x·Sy'' = (''x·y'') + ''x'' # * (6) and (7) are the recursive definition of multiplication. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Robinson arithmetic」の詳細全文を読む スポンサード リンク
|